import os
import csv
from queue import LifoQueue

csv.field_size_limit(500 * 1024 * 1024)

# 计算函数(有序列表)
def AND(a, b):
    imax = len(a)
    jmax = len(b)
    i = 0
    j = 0
    ans = []
    while i < imax and j < jmax:
        if a[i] < b[j]:
            i = i + 1
        elif a[i] > b[j]:
            j = j + 1
        else:
            ans.append(a[i])
            i = i + 1
            j = j + 1
    return ans


def OR(a, b):
    imax = len(a)
    jmax = len(b)
    i = 0
    j = 0
    ans = []
    while i < imax and j < jmax:
        if a[i] < b[j]:
            ans.append(a[i])
            i = i + 1
        elif a[i] > b[j]:
            ans.append(b[j])
            j = j + 1
        else:
            ans.append(a[i])
            i = i + 1
            j = j + 1
    while i < imax:
        ans.append(a[i])
        i = i + 1
    while j < jmax:
        ans.append(b[j])
        j = j + 1
    return ans


def NOT(a, b):
    imax = len(a)
    jmax = len(b)
    i = 0
    j = 0
    ans = []
    print(a[0])
    print(b[0])
    while i < imax and j < jmax:
        if a[i] < b[j]:
            ans.append(a[i])
            i = i + 1
        else:
            i = i + 1
            j = j + 1
    while i < imax:
        ans.append(a[i])
        i = i + 1
    return ans


def search(data_pth):
    # 倒排表
    fp_data = open(
        os.path.join(data_pth, "inverted_index.csv"), mode="r", encoding="utf-8"
    )
    # 所有id集合
    fp_id_name = open(os.path.join(data_pth, "id_name.csv"), mode="r", encoding="utf-8")
    id_name_csv=csv.reader(fp_id_name)
    next(id_name_csv)
    id_name_dict=dict()
    all_id_list=[]
    for row in id_name_csv:
        id_name_dict.update({row[0]:row[1]})
        all_id_list.append(row[0])
    

    data_csv = csv.reader(fp_data)
    next(data_csv)
    tag = []
    ids = []
    for row in data_csv:
        tag.append(row[0])
        ids.append(row[1].split(","))
    print("检索条目：", end=" ")
    print(tag)
    tag_and_alu = tag.copy()
    tag_and_alu.append("AND")
    tag_and_alu.append("OR")
    tag_and_alu.append("NOT")
    tag_and_alu.append("（")
    tag_and_alu.append("）")
    # tag-id字典
    dict_tag_ids = dict(zip(tag, ids))

    stack_alu = LifoQueue()
    stack_data = LifoQueue()

    """
    # 科幻 AND 喜剧
    stack_data.put(ids[0])
    stack_alu.put("AND")
    stack_data.put(ids[1])
    a=stack_data.get()
    b=stack_data.get()
    alu=stack_alu.get()
    if alu=="AND":
        ans=[i for i in a if i in b]
        print(ans)
    """
    # 读入键盘数据
    input_ = input("输入查询条件:")
    # 输入划分为一个个词项
    input_list = input_.split(" ")
    for i in range(len(input_list)):
        # 非法输入
        if input_list[i] not in tag_and_alu:
            print("error inpupt")
            print(i)
            return
        else:
            # tag
            if input_list[i] in tag:
                stack_data.put(dict_tag_ids[input_list[i]])
                print("读入 " + input_list[i])
                print(dict_tag_ids[input_list[i]][:5])
            # 运算符
            else:
                # 操作符栈为空则入栈
                if stack_alu.empty():
                    stack_alu.put(input_list[i])
                    print("读入 " + input_list[i])
                # 左括号入栈
                elif input_list[i] == "（":
                    stack_alu.put(input_list[i])
                    print("读入 " + input_list[i])
                # 右括号循环计算直到弹出左括号
                elif input_list[i] == "）":
                    top = stack_alu.get()
                    print("读得 " + top)
                    while top != "（":
                        if top == "NOT":
                            a = stack_data.get()
                            ans = NOT(all_id_list, a)
                            stack_data.put(ans)
                            print("计算 " + top)
                            print(ans[:5])
                        elif top == "AND":
                            a = stack_data.get()
                            b = stack_data.get()
                            ans = AND(a, b)
                            stack_data.put(ans)
                            print("计算 " + top)
                        else:
                            a = stack_data.get()
                            b = stack_data.get()
                            ans = OR(a, b)
                            stack_data.put(ans)
                            print("计算 " + top)
                        top = stack_alu.get()
                        print("读得 " + top)
                # NOT优先级最高，入栈
                elif input_list[i] == "NOT":
                    stack_alu.put(input_list[i])
                    print("读入 " + input_list[i])
                elif input_list[i] == "AND":
                    top = stack_alu.get()
                    print("读得 " + top)
                    while 1:
                        if top == "（":
                            stack_alu.put(top)
                            stack_alu.put(input_list[i])
                            print("读入 " + input_list[i])
                            break
                        elif top == "AND":
                            stack_alu.put(top)
                            stack_alu.put(input_list[i])
                            print("读入 " + input_list[i])
                            break
                        elif top == "OR":
                            stack_alu.put(top)
                            stack_alu.put(input_list[i])
                            print("读入 " + input_list[i])
                            break
                        elif top == "NOT":
                            a = stack_data.get()
                            ans = NOT(all_id_list, a)
                            stack_data.put(ans)
                            print("计算 " + top)
                        top = stack_alu.get()
                        print("读得 " + top)
                elif input_list[i] == "OR":
                    top = stack_alu.get()
                    print("读得 " + top)
                    while 1:
                        if top == "（":
                            stack_alu.put(top)
                            stack_alu.put(input_list[i])
                            print("读入 " + input_list[i])
                            break
                        elif top == "AND":
                            a = stack_data.get()
                            b = stack_data.get()
                            ans = AND(a, b)
                            stack_data.put(ans)
                            print("计算 " + top)
                        elif top == "OR":
                            stack_alu.put(top)
                            stack_alu.put(input_list[i])
                            print("读入 " + input_list[i])
                            break
                        elif top == "NOT":
                            a = stack_data.get()
                            ans = NOT(all_id_list, a)
                            stack_data.put(ans)
                            print("计算 " + top)
                        top = stack_alu.get()
                        print("读得 " + top)

    # 开始出栈
    while stack_alu.empty() != True:
        top = stack_alu.get()
        print("读得 " + top)
        if top == "AND":
            a = stack_data.get()
            b = stack_data.get()
            ans = AND(a, b)
            stack_data.put(ans)
            print("计算 " + top)
        elif top == "OR":
            a = stack_data.get()
            b = stack_data.get()
            ans = OR(a, b)
            stack_data.put(ans)
            print("计算 " + top)
        elif top == "NOT":
            a = stack_data.get()
            ans = NOT(all_id_list, a)
            stack_data.put(ans)
            print("计算 " + top)

    # 最后答案
    ans = stack_data.get()
    if "1291544" in ans:
        print("yes")
    else:
        print("no")
    for i in range(len(ans)):
        print(ans[i],end="")
        print(id_name_dict[ans[i]])
    return


if __name__ == "__main__":
    pth = os.path.split(os.path.realpath(__file__))[0]
    data_pth = os.path.join(pth, "data")
    out_pth = os.path.join(pth, "output")

    search(data_pth)
